1. Field of the Invention
The present invention relates to circuits and methods carrying out calculations on elements of a finite filed, and particularly to circuits and methods for calculating the inverse of these elements.
2. Discussion of the Related Art
A finite field is a finite set of binary numbers used, for example, to correct errors during transmission of data which are Reed-Solomon encoded.
All the binary numbers of n bits constitute a finite field of 2.sup.n =N+1 elements, in which an internal addition and multiplication are defined, such that the sum or the product of two numbers of the field is also a number of the field. The addition of two numbers is defined by a bit-to-bit Exclusive-OR between these two numbers. As a consequence, if x is an arbitrary element of the field, EQU x+x=2x=0.
The multiplication is a conventional multiplication of two binary numbers of n bits as long as it does not generate a carry, i.e., as long as the result does not have bits at 1 of a weight higher than n-1. As soon as a carry is generated, it is combined through Exclusive-OR operations with predetermined bits of the bits of weights from 0 to n-1, that are defined by a so- called generator polynomial of the finite field.
Any non-zero element of the finite field is a power of another non-zero and non-unity element of this finite field. In a finite field of N+1 elements, the powers are defined modulus, N, i.e., x.sup.i =x.sup.i+N, where x is a non-zero and non-unity element of the finite field and i is a positive or negative integer. The elements of a finite field are written 0, .alpha..sup.0, .alpha..sup.1, . . . , .alpha..sup.N-1. The elements .alpha..sup.0 to .alpha..sup.n-1 are the numbers 2.sup.0, 2.sup.1, . . . , 2.sup.n-1 constituting the base of the binary numbers of n bits.
To calculate correction coefficients in a Reed-Solomon decoder, it is necessary to calculate ratios y/x, where y and x are numbers calculated by the decoder and that may have arbitrary values. For this purpose, y is generally multiplied by the inverse of x.
To calculate an inverse, an inverse table stored in a ROM can be used. However, the use of a ROM is not adapted to an integration among other processing circuits with the existing techniques for designing integrated circuits. With these existing techniques, the ROM must be located outside an area where the other elements of the processing circuit are integrated. This causes a substantial large surface to be lost although a ROM needs a relatively small surface.
Another approach is to generate inverses in a wired manner, using logic gates. However, the number of connections between the logic gates in order to carry out the inversion function is so important that the corresponding metallizations occupy a surface equivalent to the lost surface caused by the use of a ROM, although the wired inverter can be integrated among the processing circuits.